\ifx\wholebook\relax \else
% ------------------------

\documentclass{article}
\usepackage[en]{../../../prelude}

\setcounter{page}{1}

\begin{document}

%--------------------------

% ================================================================
%                 COVER PAGE
% ================================================================

\title{AVL tree}

\author{Larry~LIU~Xinyu
\thanks{{\bfseries Larry LIU Xinyu } \newline
  Email: liuxinyu95@gmail.com \newline}
  }

\maketitle
\fi

\markboth{AVL tree}{Elementary Algorithms}

\ifx\wholebook\relax
\chapter{AVL tree}
\numberwithin{Exercise}{chapter}
\fi

% ================================================================
%                 Introduction
% ================================================================
\section{Introduction}
\label{introduction} \index{AVL tree}

\subsection{How to measure the balance of a tree?}
Besides red-black tree, are there any other intuitive self-balancing
binary search trees? In order to measure how balancing a binary search tree is,
one idea is to compare the height of the right sub-tree and left sub-tree.
If they differs a lot, the tree isn't well balanced. Let's denote the
difference height between two children as below

\be
  \delta(T) = |T_r| - |T_l|
\ee

Where $|T|$ means the height of tree $T$, and $T_l$, $T_r$ are the left
and right sub-trees.

If $\delta(T) = 0$ for every node, The tree is definitely balanced. For example, a
complete binary tree has $n=2^h-1$ nodes for height $h$. There is
no empty branches unless the leafs. Another trivial case is empty
tree. $\delta(\phi) = 0$. The less absolute value of $\delta(T)$
the more balanced the tree is.

We define $\delta(T)$ as the {\em balance factor} of a binary search
tree.

% ================================================================
% Definition
% ================================================================
\section{Definition of AVL tree}
\index{AVL tree!definition}

The AVL tree is a special binary search tree, that all sub-trees
satisfying the following criteria.

\be
  |\delta(T)| \leq 1
\ee

The absolute value of balance factor is less than or equal to 1, which
means there are only three valid values, -1, 0 and 1. Figure \ref{fig:avl-example} shows an example AVL tree.

\begin{figure}[htbp]
   \centering
   \includegraphics[scale=0.5]{img/avl-example.ps}
   \caption{AVL tree example} \label{fig:avl-example}
\end{figure}


Why AVL tree can keep the tree balanced? In other words, Can this definition
ensure the height of the tree as $O(\lg n)$ where $n$ is the number of
the nodes in the tree? Let's prove this fact.

For an AVL tree of height $h$, The number of nodes varies. It can have at
most $2^h-1$ nodes for a complete binary tree. We are interesting about
how many nodes there are at least. Let's denote the minimum number of nodes
for the AVL tree of height $h$ as $N(h)$. It's obvious we have the below
result for the trivial cases.

\begin{itemize}
\item For empty tree, $h=0$, $N(0)=0$;
\item For a singleton leaf tree, $h=1$, $N(1)=1$;
\end{itemize}

What's the situation for the common case $N(h)$? Figure \ref{fig:N-h-relation}
shows an AVL tree $T$ of height $h$. It contains three parts, the root node,
and two sub trees $T_l$, $T_r$. We have the following fact.

\be
  h= max(|T_l|, |T_r|) + 1
\ee

We immediately know that, there must be one child has height $h-1$. According
to the definition of AVL tree, we have
$||T_l|-|T_r|| \leq 1$. This leads to the fact that the height of
other tree can't be lower than $h-2$, So the total number of the nodes
of $T$ is the number of nodes in both children plus 1 (for the root node).
We exclaim that.

\be
  N(h) = N(h-1) + N(h-2) + 1
  \label{eq:Fibonacci-like}
\ee

\begin{figure}[htbp]
   \centering
   \includegraphics[scale=0.5]{img/Nh-lvr.ps}
   \caption{An AVL tree of height $h$. The height of one sub-tree is $h-1$, the other is no less than $h-2$} \label{fig:N-h-relation}
\end{figure}

This recursion reminds us the famous Fibonacci series. Actually we can
transform it to Fibonacci series by defining $N'(h) = N(h)+1$. So equation
(\ref{eq:Fibonacci-like}) changes to.

\be
  N'(h) = N'(h-1) + N'(h-2)
\ee

\begin{lemma}
\label{lemma:N-phi}
Let $N(h)$ be the minimum number of nodes for an AVL tree of
height $h$. and $N'(h) = N(h) + 1$, then
\be
  N'(h) \geq \phi^h
\ee

Where $\phi = \frac{\sqrt{5}+1}{2}$ is the golden ratio.
\end{lemma}

\begin{proof}
For the trivial case, we have
\begin{itemize}
\item $h=0$, $N'(0) = 1 \geq \phi^0 = 1$
\item $h=1$, $N'(1) = 2 \geq \phi^1 = 1.618...$
\end{itemize}

For the induction case, suppose $N'(h) \geq \phi^h$.
\[
  \begin{array}{lll}
  N'(h+1) & = N'(h) + N'(h-1) & \{Fibonacci\} \\
          & \geq \phi^h + \phi^{h-1} & \\
          & = \phi^{h-1}(\phi + 1) & \{\phi + 1 = \phi^2 = \frac{\sqrt{5}+3}{2}\} \\
          & = \phi^{h+1}
 \end{array}
\]
\end{proof}

From Lemma \ref{lemma:N-phi}, we immediately get

\be
  h \leq log_{\phi}(n+1) = log_{\phi}2 \cdot \lg (n+1) \approx 1.44 \lg (n+1)
  \label{eq:AVL-height}
\ee

It tells that the height of AVL tree is proportion to $O(\lg n)$, which
means that AVL tree is balanced.

For the mutate operations such as tree insertion and deletion,
if the balance factor changes to any invalid values, some fixing has
to be performed to resume $|\delta|$ within 1. Most implementations utilize
tree rotations. In this chapter, we'll show the pattern matching solution
which is inspired by Okasaki's red-black tree solution\cite{okasaki}.
Because of this `modify-fix' approach, AVL tree is also a kind of
self-balancing binary search tree. For comparison purpose, we'll also
show the procedural algorithms.

Of course we can compute the $\delta$ value recursively, another option
is to store the balance factor inside each nodes, and update them
when we modify the tree. The latter one avoid computing the same value
every time.

Based on this idea, we can add one extra data field $\delta$ to the
binary search tree definition. The following C++ example code reflects
this change \footnote{Some implementations store the height of a tree instead of $\delta$ as in \cite{py-avl}}.

\lstset{language=C++}
\begin{lstlisting}
template <class T>
struct node {
    int delta;
    T key;
    node* left;
    node* right;
    node* parent;
};
\end{lstlisting}

In purely functional setting, some implementation use different
constructors to store the $\delta$ information. for example in
\cite{hackage}, there are 4 constructors, \texttt{E}, \texttt{N}, \texttt{P}, \texttt{Z} defined.
\texttt{E} for empty tree, \texttt{N} for tree with negative 1 balance factor,
\texttt{P} for tree with positive 1 balance factor and \texttt{Z} for zero case.

In this chapter, we'll explicitly store the balance factor inside
the node.

\lstset{language=Haskell}
\begin{lstlisting}
data AVLTree a = Empty
               | Br (AVLTree a) a (AVLTree a) Int
\end{lstlisting}

The immutable operations, including looking up, finding the maximum
and minimum elements are all same as the binary search tree. We'll
skip them and focus on the mutable operations.

% ================================================================
%                 Insertion
% ================================================================
\section{Insertion}
\index{AVL tree!insertion}

Insert a new element to the tree may violate the AVL tree property
that the absolute value of $\delta$ exceeds 1. To resume it, one option
is to do the tree rotation according to the different insertion cases.
Most implementation is based on this approach

Another way is to use the similar pattern matching method mentioned by
Okasaki in his red-black tree implementation \cite{okasaki}. Inspired
by this idea, it is possible to provide a simple and intuitive
solution.

When insert a new key to the AVL tree, the balance factor of the
root may {\em changes} in range $[-1, 1]$\footnote{Note that, it doesn't mean $\delta$ is in range $[-1, 1]$, the changes of $\delta$ is in this range.},
and the height may increase
at most by one, which we need recursively use this information
to update the $\delta$ value in further level nodes. We can define
the result of the insertion algorithm as a pair of data
$(T', \Delta H)$. Where $T'$ is the new tree and $\Delta H$ is the
increment of height. Let's denote function $first(pair)$
can return the first element in a pair. We can modify
the binary search tree insertion algorithm as the following to
handle AVL tree.

\be
insert(T, k) = first(ins(T, k))
\ee

where

\be
ins(T, k) = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  ((\phi, k, \phi, 0), 1) & T = \phi \\
  tree(ins(T_l, k), k', (T_r, 0), \Delta) & k < k' \\
  tree((T_l, 0), k', ins(T_r, k), \Delta) & otherwise
  \end{array}
\right.
\label{eq:ins}
\ee

$T_l, T_r, k', \Delta$ represent the left child, right child, the key and
the balance factor of a tree.

\[
  \begin{array}{l}
  T_l = left(T) \\
  T_r = right(T) \\
  k' = key(T) \\
  \Delta = \delta(T)
  \end{array}
\]

When we insert a new key $k$ to a AVL tree $T$, if the tree is
empty, we create a leaf with $k$ as the key, set the balance
factor as 0, and the height is increased by one.

If $T$ isn't empty, we need compare the key $k'$ with $k$.
If $k$ is less than the key, we recursively insert it to the left
child, otherwise we insert it to the right.

As the result of the recursive insertion is a
pair like $(T_l', \Delta H_l)$, we need do balance adjustment and
update the increment of height. Function $tree()$ is defined
to dealing with this task. It takes 4 parameters as $(T_l', \Delta H_l)$,
$k'$, $(T_r', \Delta H_r)$, and $\Delta$. The result of this function
is defined as $(T', \Delta H)$, where $T'$ is the new tree after
adjustment, and $\Delta H$ is the new increment of height. It is
defined as below.

\be
  \Delta H = |T'| - |T|
\ee

This can be further detailed deduced in 4 cases.

\be
\begin{array}{rl}
  \Delta H & = |T'| - |T| \\
              & = 1 + max(|T_r'|, |T_l'|) - (1 + max(|T_r|, |T_l|)) \\
              & = max(|T_r'|, |T_l'|) - max(|T_r|, |T_l|) \\
              & = \left \{
                  \begin{array}{r@{\quad:\quad}l}
                  \Delta H_r & \Delta \geq 0 \land \Delta' \geq 0 \\
                  \Delta + \Delta H_r & \Delta \leq 0 \land \Delta' \geq 0 \\
                  \Delta H_l - \Delta & \Delta \geq 0 \land \Delta' \leq 0 \\
                  \Delta H_l & otherwise
                  \end{array} \right .
\end{array}
\ee

The proof of this equation can be referred from Appendix C.

The next problem is to determine the new balance
factor $\Delta'$ before performing balance adjustment.
According to the definition of AVL tree, the balance factor is the
height difference of the right and left sub trees. We have
the following fact.

\be
\begin{array}{rl}
\Delta' & = |T_r'| - |T_l'| \\
        & = |T_r| + \Delta H_r - (|T_l| + \Delta H_l) \\
        & = |T_r| - |T_l| + \Delta H_r - \Delta H_l \\
        & = \Delta + \Delta H_r - \Delta H_l
\end{array}
\ee

With all these changes in height and the balance factor, we can
define the $tree()$ function mentioned in (\ref{eq:ins}).

\be
tree((T_l', \Delta H_l), k, (T_r', \Delta H_r), \Delta) =
  balance ((T_l', k, T_r', \Delta'), \Delta H)
\ee

Before we moving into details of balance adjustment, let's translate
the above equations to example Haskell program.

First is the insert function.

\lstset{language=Haskell}
\begin{lstlisting}
insert::(Ord a)=>AVLTree a -> a -> AVLTree a
insert t x = fst $ ins t where
    ins Empty = (Br Empty x Empty 0, 1)
    ins (Br l k r d)
        | x < k     = tree (ins l) k (r, 0) d
        | x == k    = (Br l k r d, 0)
        | otherwise = tree (l, 0) k (ins r) d
\end{lstlisting} %$

Here we also handle the duplicated keys (the key has already existed.) by overwriting.

\begin{lstlisting}
tree::(AVLTree a, Int) -> a -> (AVLTree a, Int) -> Int -> (AVLTree a, Int)
tree (l, dl) k (r, dr) d = balance (Br l k r d', delta) where
    d' = d + dr - dl
    delta = deltaH d d' dl dr
\end{lstlisting}

And the definition of height increment is as below.

\begin{lstlisting}
deltaH :: Int -> Int -> Int -> Int -> Int
deltaH d d' dl dr
       | d >=0 && d' >=0 = dr
       | d <=0 && d' >=0 = d+dr
       | d >=0 && d' <=0 = dl - d
       | otherwise = dl
\end{lstlisting}

\subsection{Balancing adjustment}
\index{AVL tree!balancing}
As the pattern matching approach is adopted in doing re-balancing.
We need consider what kind of patterns violate the AVL tree property.

Figure \ref{fig:avl-insert-fix} shows the 4 cases which need fix. For all
these 4 cases the balancing factors are either -2, or +2 which exceed
the range of $[-1, 1]$. After balancing adjustment, this factor turns
to be 0, which means the height of left sub tree is equal to the right
sub tree.

\begin{figure}[htbp]
   \begin{center}
     \setlength{\unitlength}{1cm}
     \begin{picture}(15, 15)
        % arrows
        \put(4.5, 9.5){\vector(1, -1){1}}
        \put(4.5, 5){\vector(1, 1){1}}
        \put(10, 9.5){\vector(-1, -1){1}}
        \put(10, 5){\vector(-1, 1){1}}
        % delta values
        \put(5, 13){$\delta(z) = -2$}
        \put(2.5, 12){$\delta(y) = -1$}
        \put(10, 13){$\delta(x) = 2$}
        \put(11.5, 11.5){$\delta(y) = 1$}
        \put(1.5, 5.5){$\delta(z) = -2$}
        \put(3.5, 4){$\delta(x) = 1$}
        \put(12, 5.5){$\delta(x) = 2$}
        \put(10.5, 4){$\delta(z) = -1$}
        \put(7.5, 10){$\delta'(y) = 0$}
        % graphics
	    \put(0, 7){\includegraphics[scale=0.5]{img/avl-insert-ll.ps}}
        \put(0, 0){\includegraphics[scale=0.5]{img/avl-insert-lr.ps}}
        \put(7, 7){\includegraphics[scale=0.5]{img/avl-insert-rr.ps}}
        \put(8.5, 0){\includegraphics[scale=0.5]{img/avl-insert-rl.ps}}
        \put(2, 5){\includegraphics[scale=0.5]{img/avl-insert-fixed.ps}}
      \end{picture}
     \caption{4 cases for balancing a AVL tree after insertion} \label{fig:avl-insert-fix}
  \end{center}
\end{figure}

We call these four cases left-left lean, right-right lean, right-left lean,
and left-right lean cases in clock-wise direction from top-left. We denote
the balancing factor before fixing as $\delta(x), \delta(y)$, and $\delta(z)$, while after fixing, they changes to $\delta'(x), \delta'(y)$, and
$\delta'(z)$ respectively.

After fixing, we have $\delta(y)=0$ for all four cases. The result values of $\delta'(x)$ and $\delta'(z)$ can be given as below. The proof are provided in Appendix C.

\subsubsection*{Left-left lean}

\be
  \begin{array}{l}
  \delta'(x) = \delta(x) \\
  \delta'(y) = 0 \\
  \delta'(z) = 0
  \end{array}
\ee

\subsubsection*{Right-right lean}

\be
  \begin{array}{l}
  \delta'(x) = 0 \\
  \delta'(y) = 0 \\
  \delta'(z) = \delta(z)
  \end{array}
  \label{eq:rr-result}
\ee

\subsubsection*{Right-left lean and Left-right lean}

\be
  \begin{array}{l}
  \delta'(x) = \left \{
    \begin{array}
    {r@{\quad:\quad}l}
    -1 & \delta(y) = 1 \\
    0 & otherwise
    \end{array}
    \right. \\
  \delta'(y) = 0 \\
  \delta'(z) = \left \{
    \begin{array}
    {r@{\quad:\quad}l}
    1 & \delta(y) = -1 \\
    0 & otherwise
    \end{array}
    \right.
  \end{array}
  \label{eq:rl-result}
\ee

\subsection{Pattern Matching}
The pattern matching fixing function can be given as the following.

\be
balance(T, \Delta H) = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  (((A, x, B, \delta(x)), y, (C, z, D, 0), 0), \Delta H - 1) & P_{ll}(T) \\
  (((A, x, B, 0), y, (C, z, D, \delta(z)), 0), \Delta H - 1) & P_{rr}(T) \\
  (((A, x, B, \delta'(x)), y, (C, z, D, \delta'(z)), 0), \Delta H - 1) & P_{rl}(T) \lor P_{lr}(T) \\
  (T, \Delta H) & otherwise
  \end{array}
\right.
\ee

Where $P_{ll}(T)$ means the pattern of tree $T$ is left-left lean respectively. $\delta'(x)$ and $delta'(z)$ are defined in (\ref{eq:rl-result}). The four patterns are tested as below.

\be
\begin{array}{l}
P_{ll}(T): T = (((A, x, B, \delta(x)), y, C, -1), z, D, -2) \\
P_{rr}(T): T = (A, x, (B, y, node(C, z, D, \delta(z)), 1), 2) \\
P_{rl}(T): T = ((A, x, (B, y, C, \delta(y)), 1), z, D, -2) \\
P_{lr}(T): T = (A, x, ((B, y, C, \delta(y)), z, D, -1), 2)
\end{array}
\ee

Translating the above function definition to Haskell yields a simple
and intuitive program.

\begin{lstlisting}
balance (Br (Br (Br a x b dx) y c (-1)) z d (-2), _) =
        (Br (Br a x b dx) y (Br c z d 0) 0, 0)
balance (Br a x (Br b y (Br c z d dz)    1)    2, _) =
        (Br (Br a x b 0) y (Br c z d dz) 0, 0)
balance (Br (Br a x (Br b y c dy)    1) z d (-2), _) =
        (Br (Br a x b dx') y (Br c z d dz') 0, 0) where
    dx' = if dy ==  1 then -1 else 0
    dz' = if dy == -1 then  1 else 0
balance (Br a x (Br (Br b y c dy) z d (-1))    2, _) =
        (Br (Br a x b dx') y (Br c z d dz') 0, 0) where
    dx' = if dy ==  1 then -1 else 0
    dz' = if dy == -1 then  1 else 0
balance (t, d) = (t, d)
\end{lstlisting}

The insertion algorithm takes time proportion to the height of the
tree. As AVL is balanced according to (\ref{eq:AVL-height}), its performance
is $O(\lg n)$ where $n$ is the number of elements stored in the AVL
tree.

\subsubsection{Verification}
\index{AVL tree!verification}
When verify if a tree is AVL tree, we need verify two things,
first, it's a binary search tree; second, it satisfies AVL tree property.

In order to test if a binary tree satisfies AVL tree property, we can
examine the height difference between the two sub trees recursively
till the leaves.

\be
  avl?(T) = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  True & T = \phi \\
  avl?(T_l) \land avl?(T_r) \land ||T_r|-|T_l|| \leq 1 & otherwise
  \end{array}
  \right .
\ee

Where the height can also be calculated recursively.

\be
  |T| = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  0 & T = \phi \\
  1 + max(|T_r|, |T_l|) & otherwise
  \end{array}
  \right .
\ee

The corresponding Haskell example program is given as the following.

\begin{lstlisting}
isAVL :: (AVLTree a) -> Bool
isAVL Empty = True
isAVL (Br l _ r d) = and [isAVL l, isAVL r, abs (height r - height l) <= 1]

height :: (AVLTree a) -> Int
height Empty = 0
height (Br l _ r _) = 1 + max (height l) (height r)
\end{lstlisting}

\begin{Exercise}
Write a program to verify if a tree is the AVL tree.
Please consider both functional and imperative approaches.
\end{Exercise}



% ================================================================
%                 Deletion
% ================================================================

\section{Deletion}
\index{AVL tree!deletion}

As we mentioned before, deletion will not be a major problem in
purely functional settings. As the tree is read only, the use case
is typically performing looking up after build.

For purely functional deletion, it actually re-builds the tree
as we show in the chatper of red-black tree. We put the AVL
tree deletion algorithm in Appendix C.

\section{Imperative AVL tree algorithm $\star$}
\index{AVL tree!imperative insertion}

This section shows the traditional insert-and-rotate
approach to realize AVL tree insertion algorithm.

Similar to the red-black tree algorithm, the strategy
is to first do the binary search tree insertion,
then fix the balance by rotation and return the final result.

\begin{algorithmic}[1]
\Function{Insert}{$T, k$}
  \State $root \gets T$
  \State $x \gets$ \Call{Create-Leaf}{$k$}
  \State \Call{$\delta$}{$x$} $\gets 0$
  \State $parent \gets$ NIL
  \While{$T \neq$ NIL}
    \State $parent \gets T$
    \If{$k <$ \Call{Key}{$T$}}
      \State $T \gets $ \Call{Left}{$T$}
    \Else
      \State $T \gets $ \Call{Right}{$T$}
    \EndIf
  \EndWhile
  \State \Call{Parent}{$x$} $\gets parent$
  \If{$parent =$ NIL} \Comment{tree $T$ is empty}
    \State \Return $x$
  \ElsIf{$k <$ \Call{Key}{$parent$}}
    \State \Call{Left}{$parent$} $\gets x$
  \Else
    \State \Call{Right}{$parent$} $\gets x$
  \EndIf
  \State \Return \Call{AVL-Insert-Fix}{$root, x$}
\EndFunction
\end{algorithmic}

Note that after insertion, the balance factor $\delta$ may change because
the height of the tree can grow. Inserting on right side can
increase $\delta$ by 1, while insert on left side can decrease it. By
the end of this algorithm, we need perform bottom-up fixing from node $x$
towards root.

We can translate the pseudo code to Python example program\footnote{C and C++ source code are available along with this book}.
\lstset{language=Python}
\begin{lstlisting}
def avl_insert(t, key):
    root = t
    x = Node(key)
    parent = None
    while(t):
        parent = t
        if(key < t.key):
            t = t.left
        else:
            t = t.right
    if parent is None: #tree is empty
        root = x
    elif key < parent.key:
        parent.set_left(x)
    else:
        parent.set_right(x)
    return avl_insert_fix(root, x)
\end{lstlisting}

This is a top-down algorithm. It searches the tree from root down to the proper
position and inserts the new key as a leaf. By the end of this algorithm, it calls the fixing function with the root and the new inserted node.

Note that we reuse the same methods of \texttt{set\_left()} and \texttt{set\_right()} as
we defined in chapter of red-black tree.

In order to resume the AVL tree property, we first check if the new node is inserted on left or right. If it is on left, the balance factor $\delta$ decreases, otherwise it increases. If we denote the new value as $\delta'$, there are 3 cases between $\delta$ and $\delta'$.

\begin{itemize}
\item If $|\delta| = 1$ and $|\delta'| = 0$, it means the new node makes the tree perfectly balanced, the height of the parent node doesn't change, the algorithm can be terminated.

\item If $|\delta| = 0$ and $|\delta'| = 1$, it means either the left or the right sub tree increases its height. We need go on checking the upper level of the tree.

\item If $|\delta| = 1$ and $|\delta'| = 2$, it means the AVL tree property is violated due to the new insertion. We need perform rotation to fix it.
\end{itemize}

\begin{algorithmic}[1]
\Function{AVL-Insert-Fix}{$T, x$}
  \While{\Call{Parent}{$x$} $\neq$ NIL}
    \State $\delta \gets $ \textproc{$\delta$}(\Call{Parent}{$x$})
    \If{$x = $ \textproc{Left}(\Call{Parent}{$x$})}
      \State $\delta' \gets \delta - 1$
    \Else
      \State $\delta' \gets \delta + 1$
    \EndIf
    \State \textproc{$\delta$}(\Call{Parent}{$x$}) $\gets \delta'$
    \State $P \gets $ \Call{Parent}{$x$}
    \State $L \gets $ \Call{Left}{$x$}
    \State $R \gets $ \Call{Right}{$x$}
    \If{$|\delta| = 1$ and $|\delta'| = 0$} \Comment{Height doesn't change, terminates.}
      \State \Return $T$
    \ElsIf{$|\delta| = 0$ and $|\delta'| = 1$} \Comment{Go on bottom-up updating.}
      \State $x \gets P$
    \ElsIf{$|\delta| = 1$ and $|\delta'| = 2$}
      \If{$\delta'=2$}
        \If{$\delta(R) = 1$} \Comment{Right-right case}
          \State $\delta(P) \gets 0$ \Comment{By (\ref{eq:rr-result})}
          \State $\delta(R) \gets 0$
          \State $T \gets $ \Call{Left-Rotate}{$T, P$}
        \EndIf
        \If{$\delta(R) = -1$} \Comment{Right-left case}
          \State $\delta_y \gets $ \textproc{$\delta$}(\Call{Left}{$R$}) \Comment{By (\ref{eq:rl-result})}
          \If{$\delta_y = 1$}
            \State $\delta(P) \gets -1$
          \Else
            \State $\delta(P) \gets 0$
          \EndIf
          \State \textproc{$\delta$}(\Call{Left}{$R$}) $\gets 0$
          \If{$\delta_y = -1$}
            \State $\delta(R) \gets 1$
          \Else
            \State $\delta(R) \gets 0$
          \EndIf
          \State $T \gets $ \Call{Right-Rotate}{$T, R$}
          \State $T \gets $ \Call{Left-Rotate}{$T, P$}
        \EndIf
      \EndIf
      \If{$\delta' = -2$}
        \If{$\delta(L) = -1$} \Comment{Left-left case}
          \State $\delta(P) \gets 0$
          \State $\delta(L) \gets 0$
          \State \Call{Right-Rotate}{$T, P$}
        \Else \Comment{Left-Right case}
          \State $\delta_y \gets $ \textproc{$\delta$}(\Call{Right}{$L$})
          \If{$\delta_y = 1$}
            \State $\delta(L) \gets -1$
          \Else
            \State $\delta(L) \gets 0$
          \EndIf
          \State \textproc{$\delta$}(\Call{Right}{$L$}) $\gets 0$
          \If{$\delta_y = -1$}
            \State $\delta(P) \gets 1$
          \Else
            \State $\delta(P) \gets 0$
          \EndIf
          \State \Call{Left-Rotate}{$T, L$}
          \State \Call{Right-Rotate}{$T, P$}
        \EndIf
      \EndIf
      \State break
    \EndIf
  \EndWhile
  \State \Return $T$
\EndFunction
\end{algorithmic}

As rotation operation doesn't update the balance factor $\delta$,
we need update it for impacted nodes. Among the four cases, the right-right case and the left-left case need only one rotation, while the right-left case and the left-right case need two rotations.

The relative example python program is as the following.

\begin{lstlisting}
def avl_insert_fix(t, x):
    while x.parent is not None:
        d2 = d1 = x.parent.delta
        if x == x.parent.left:
            d2 = d2 - 1
        else:
            d2 = d2 + 1
        x.parent.delta = d2
        (p, l, r) = (x.parent, x.parent.left, x.parent.right)
        if abs(d1) == 1 and abs(d2) == 0:
            return t
        elif abs(d1) == 0 and abs(d2) == 1:
            x = x.parent
        elif abs(d1)==1 and abs(d2) == 2:
            if d2 == 2:
                if r.delta == 1:  # Right-right case
                    p.delta = 0
                    r.delta = 0
                    t = left_rotate(t, p)
                if r.delta == -1: # Right-Left case
                    dy = r.left.delta
                    if dy == 1:
                        p.delta = -1
                    else:
                        p.delta = 0
                    r.left.delta = 0
                    if dy == -1:
                        r.delta = 1
                    else:
                        r.delta = 0
                    t = right_rotate(t, r)
                    t = left_rotate(t, p)
            if d2 == -2:
                if l.delta == -1: # Left-left case
                    p.delta = 0
                    l.delta = 0
                    t = right_rotate(t, p)
                if l.delta == 1: # Left-right case
                    dy = l.right.delta
                    if dy == 1:
                        l.delta = -1
                    else:
                        l.delta = 0
                    l.right.delta = 0
                    if dy == -1:
                        p.delta = 1
                    else:
                        p.delta = 0
                    t = left_rotate(t, l)
                    t = right_rotate(t, p)
            break
    return t
\end{lstlisting}

We put the AVL tree deletion algorithm in appendix C for reference.

\section{Chapter note}
AVL tree was invented in 1962 by Adelson-Velskii and Landis\cite{wiki-avl},
\cite{TFATP}. The name AVL tree comes from the two inventor's name. It's earlier than red-black tree.

It's very common to compare AVL tree and red-black tree, both are self-balancing binary search trees, and for all the major operations, they both consume $O(\lg n)$ time. From the result of (\ref{eq:AVL-height}), AVL tree is more rigidly balanced hence they are faster than red-black tree in looking up intensive applications \cite{wiki-avl}. However, red-black trees could perform better in frequently insertion and removal cases.

Many popular self-balancing binary search tree libraries are implemented on top of red-black tree such as STL etc. However, AVL tree provides an intuitive and effective solution to the balance problem as well.

After this chapter, we'll extend the tree data structure from storing data in node to storing information on edges. It leads to Radix trees. If we extend the number of children from two to more, we can get B-tree. These data structures will be introduced in the next chapters.

\begin{thebibliography}{99}

\bibitem{hackage}
Data.Tree.AVL \url{http://hackage.haskell.org/packages/archive/AvlTree/4.2/doc/html/Data-Tree-AVL.html}

\bibitem{okasaki}
Chris Okasaki. ``FUNCTIONAL PEARLS Red-Black Trees in a Functional Setting''. J. Functional Programming. 1998

\bibitem{wiki-avl}
Wikipedia. ``AVL tree''. \url{http://en.wikipedia.org/wiki/AVL_tree}

\bibitem{TFATP}
Guy Cousinear, Michel Mauny. ``The Functional Approach to Programming''. Cambridge University Press; English Ed edition (October 29, 1998). ISBN-13: 978-0521576819

\bibitem{py-avl}
Pavel Grafov. ``Implementation of an AVL tree in Python''. \url{http://github.com/pgrafov/python-avl-tree}
\end{thebibliography}

\ifx\wholebook\relax\else
\end{document}
\fi

% LocalWords:  AVL Okasaki STL
